import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class Test {
    public static int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            count += map.getOrDefault(sum - k, 0);
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return count;
    }

    public static int[][] matrixBlockSum(int[][] mat, int k) {
        //构建前缀和矩阵
        int n = mat.length;
        int m = mat[0].length;
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        int[][] ans = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int r1 = (i - k <= 0 ? 1 : i - k + 1);
                int c1 = (j - k <= 0 ? 1 : j - k + 1);
                int r2 = (i + k > n ? n : i + k + 1);
                int c2 = (j + k > m ? m : j + k + 1);
                ans[i][j] = dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
            }
        }
        return ans;
    }

    public static void main1(String[] args) {
        int[] arr = {1,1,0,0,0,0};
        System.out.println(subarraySum(arr, 2));
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        matrixBlockSum(mat,1);
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            //进窗口
            sum += nums[right];

            //出窗口
            while(sum > target) {
                sum -= nums[left++];
            }

            //更新数据
            if(sum == target) {
                minLength = Math.min(minLength, right - left + 1);
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        minSubArrayLen(11,arr);
        Set<Integer>
    }
}
